package com.leetcode.offer.chapter2;

import com.leetcode.basic.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Dennis Li
 * @date 2020/7/11 19:06
 */
public class BuildTree_07 {

    /*
     * 前序遍历 preorder = [3,9,20,15,7]
     * 中序遍历 inorder = [9,3,15,20,7]
     * */

    // 散列用于存储中序遍历对应的序号
    Map<Integer, Integer> indice;

    // 已知中序和前序，重构二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 && inorder.length == 0) return null;

        indice = new HashMap<>();

        for (int i = 0; i < inorder.length; i++) {
            // 通过值来查找序号 -- 所有值互不相等
            indice.put(inorder[i], i);
        }

        TreeNode root = buildTree(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);
        return root;
    }

    /**
     * @param pre 前序序列
     * @param preStart 前序的起始位置
     * @param preEnd 前序的终止位置
     * @param in 中序序列
     * @param inStart 中序的起始位置
     * @param inEnd 中序的结束位置
     * @return 构造好的节点
     */
    // v -- 前序，k -- 中序
    public TreeNode buildTree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
        if (preStart > preEnd) return null;
        // 先序的开始即为根节点的值
        int rootVal = pre[preStart];
        TreeNode root = new TreeNode(rootVal);
        if (preStart != preEnd) {
            // 获取根节点的对应序号
            int rootIndex = indice.get(rootVal);
            // 中序遍历序列 -- 根节点左边都是左子树，右边都是右子树
            // 求解左子树结点的数量和右节点数量 -- 分治思想
            int leftNodes = rootIndex - inStart, rightNodes = inEnd - rootIndex;
            // 序列切分 -- 注意同时切分先序和中序序列
            /**
             * 1. 通过中序来确定左右结点的个数
             * 2. 通过结点个数对先序序列进行切分
             * 3. 通过根节点序号对中序序列切分
             */
            // 第一个结点被用作根节点了，所以要跳过
            root.left = buildTree(pre, preStart + 1, preStart + leftNodes, in, inStart, rootIndex - 1);
            root.right = buildTree(pre, preEnd - rightNodes + 1, preEnd, in, rootIndex + 1, inEnd);
        }
        return root;
    }

}
